大致上，所有的樹狀結構我們都已經完成講解了
今天要來介紹 Extended Binary Tree

何謂延伸二元樹

我們曾經說過，當一個 Binary Tree 有 N 節點，則會有 N + 1 個 null Link。
此時，我們將這些 null 變成一種特殊的節點，稱為 external nodes，或 Failure Nodes
其他的就叫做 internal node。

路徑長

我們來定義 2 種路徑長

1. 內部路徑長（Internal path length, I）：所有 internal node 到 root 的路徑長加總
2. 外部路徑長（External path length, E）：所有 External node 到 root 的路徑長加總

那這邊有一個定理：E = I + 2N。其中 N 為內部節點數量。我們來證明一下

數學歸納法

1. 當 N = 0 時，E = I = 0 初值成立
2. 假設 N <= (n - 1) 時成立
3. 則當 N = n，另 IL = 左子樹的內部路徑長，IR = 右子樹的內部路徑長，EL = 左子樹的外部路徑長，ER = 右子樹的外部路徑長。NL = 左子樹的內部節點總數，NR = 右子樹的內部節點總數。
   所以這棵樹的 I = IL + IR + (NL + NR)，這是因為是子樹，所以離 root 的距離會比只看左子樹的 root ，每個節點都還多 1。
4. 而外部路徑長也是同個道理：E = EL + ER + (NL + 1 + NR + 1)。因為子樹的外部節點數量 = N + 1
5. 那我們展開來看：因為 左子樹和右子樹的節點數都一定 <= n - 1，所以根據假設：
   E = IL + 2NL + IR + 2NR + NL + 1 + NR + 1 = (IL + IR + NL + NR) + 2 * (NL + NR + 1) = I + 2N
6. 根據數學歸納法，得證。

WEPL Weighted External path length

加權外部路徑長 WEPL，指的是會賦予每個外部節點一個加權值，而這棵樹的 E，算法就變成，path 長度必須乘上加權值再加總起來。

而因為有加權值的影響，因此不能夠保證，高度越高的樹，E 越大。
而這時候就衍生出了新的議題：如何求出 WEPL 最小值

求 WEPL 最小值

明天我們要來介紹的 Huffman 演算法，就是要來求 WEPL 的最小值。而這個演算法是非常有名的，甚至可以創造出大名鼎鼎的 Huffman code，是一個重要的編碼標準。